class Solution {
public:
    int distinctSubseqII(string s) {
        int all = 1, newAdd = 0;
        vector<int> dp(26, 0);
        int mod = 1e9 + 7;
        for (int i = 0; i < s.size(); i++)
        {
            int tmp = s[i] - 'a';
            newAdd = (all - dp[tmp] + mod) % mod;
            dp[tmp] = (dp[tmp] + newAdd) % mod;
            all = (all + newAdd) % mod;
        }
        int ans = (all - 1 + mod) % mod;
        return ans;
    }
};